/***********************************
定义:
    dp[i][j]: 从点i走到点0再走到点j并且经过从第0到第max(i, j)个点仅一次的最短距离。
    d[i][j]: 从i到j的折线距离
    ds[i][j]: i到j的直线距离
初始化:
    ds[i][j] = -1, 表示未计算
    d[i][j] = -1
    dp[i][j] = -1;
递推
    d[i][j] = {  //这里只考虑i<j的情况, 因为d[j][i] = d[i][j]
        ds[i][i+1], i+1=j
        ds[i][i+1] + d[i+1][j], i+1<j
    } 
    dp[i][j] =  { //这里只考虑i<=j的情况, 当i>j时有dp[i][j]=dp[j][i]
        d[0][j], i=0
        dp[i][i+1]+d[i+1][j], i+1<j
        min{dp[i][k]+ds[k][j]} =  
            min{dp[k][i]+ds[k][j]}, i+1=j, k=0..i-1
        dp[i-1][j] + ds[i-1][j], i==j
    } 

************************************/

#include <vector>
#include <array>
#include <cfloat>
#include <math.h>
#include <algorithm>
#include <stdio.h>

using std::vector;
using std::array;
using std::sort;

typedef array<double, 2> Pointer; //点
typedef vector<double> FV; 
typedef vector<int> IV;
typedef vector<Pointer> PV;
class Map {
public:
    PV &pv;
private:
    vector<FV> ds;  //记录图上任意两点的直线距离
    vector<FV> d;  //记录图上任意两点的折线距离
    vector<FV> dp; 
    IV path; //记录确定最优子问题时右点的下一跳。
public:
    Map(PV &pv) : pv(pv) {};
    double bitonic_tours(void);
    void bt_print_path(void);
private:
    double bitonic_tours_core(int i, int j);
    void bt_print_path_core(int cur, IV &vv1, IV &vv2);
    double d_dp(int i, int j);
    double get_dis(int i, int j);
};


//针对上述代码进行精简和优化。
void Map::bt_print_path(void) {
    int rp = pv.size()-1;
    IV vv1; //记录rp的起跳路线
    IV vv2; //距离rp起跳路线的补路线
    //将环路从(rp-1, rp)处断开
    vv1.push_back(rp); 
    vv2.push_back(--rp); 
    bt_print_path_core(rp, vv1, vv2);
    for(int i=vv1.size()-1; i>=0; i--) {
        printf("(%.2f, %.2f) ", pv[vv1[i]][0], pv[vv1[i]][1]);
    }
    for(int i=0; i<vv2.size(); i++) {
        printf("(%.2f, %.2f) ", pv[vv2[i]][0], pv[vv2[i]][1]);
    }
    putchar('\n');
}

void Map::bt_print_path_core(int cur, IV &vv1, IV &vv2) {
    /********************************
    *cur+1已入栈vv1, cur已入栈vv2, cur及其右边的点均已入栈。
    *******************************/
    if(!cur) { //到达起点
        vv1.push_back(0); //起点(cur)已经入栈vv2, 也要入栈vv1
        return; //路径探索完毕，开始回升。
    }
    //获取当前情况dp[cur][cur+1]的最优下一跳
    int next = path[cur+1];
        
    vv1.push_back(next);
    while(--cur>next) {
        vv2.push_back(cur);
    } 
    bt_print_path_core(next, vv2, vv1);
}


double Map::bitonic_tours(void) {
    int size = pv.size();
    if(size < 2) return -1; 
    path = IV(size);
    sort(pv.begin(), pv.end(),
        [](Pointer  &p1, Pointer &p2) -> bool 
            {return p1[0]<p2[0];}
    );
    ds = vector<FV>(size, FV(size, -1));    
    d = dp = ds;
    /**********************
    bitonic_tours_core(size-2, size-1);
    dp[size-1][size-1] = dp[size-2][size-1] + get_dis(size-2, size-1);
    return dp[size-1][size-1];
    *********************/
    return bitonic_tours_core(size-1, size-1);
}

double Map::get_dis(int i, int j) {
    if(ds[i][j]>0) return ds[i][j];
    int dx = pv[i][0]-pv[j][0];
    int dy = pv[i][1]-pv[j][1];
    ds[i][j] = pow(dx*dx+dy*dy, 0.5);
    return ds[i][j];
}

double Map::d_dp(int i, int j) {
    if(d[i][j]>0) return d[i][j];
    if(i+1==j) {
        d[i][j] = get_dis(i, j);
    }else {
        d[i][j] = get_dis(i, i+1)+d_dp(i+1, j);
    }
    return d[i][j];
}

double Map::bitonic_tours_core(int i, int j) {
    if(dp[i][j]>0) return dp[i][j];
    if(i==0) {
        dp[0][j] = d_dp(0, j);
    } else if(i+1<j) {
        dp[i][j] = bitonic_tours_core(i, i+1) + d_dp(i+1, j);
    }else { //i+1==j
        dp[i][j] = DBL_MAX;
        for(int k=0; k<i; k++) {
            double td = bitonic_tours_core(k, i)+get_dis(k, j);
            if(td < dp[i][j]) {
                dp[i][j] = td;
                path[j] = k; 
                    //记录端点坐标相邻时的最优解
                    //最右点比较特殊，只有最右点会出现i和j相等的情况，且仅一次
                    //对于最右点j有path[j](dp[j][j]) = path[j](dp[j-1][j])
            }               
                           
        }
    }
    return dp[i][j];
}

int main(void) {
    PV pv {
        {0, 6}, {1, 0}, {2, 3}, {5, 4},
        {6, 1}, {7, 5}, {8, 2}       
    };
    Map m(pv);
    printf("bitonic-tours: %f\n", m.bitonic_tours());
    m.bt_print_path();
    return 0;
}
